package developer.算法.普通数组.轮转数组;

/**
 * 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p> 4 7
 * 输入: nums = [1,2,3,1    ,5,6,4], k = 3
 * 输出: [5,6,7,1,2,3,4]
 * 1  2  3 4
 * 2  1 3 4
 * 3 1 2 4
 * 4 1 2 3
 * ->>>>>>>>>>>>>
 *
 *
 *
 *
 *
 *
 *
 * <p>
 * 解释:
 * 向右轮转 1 步: [7,1,2,3,4,5,6]
 * 向右轮转 2 步: [6,7,1,2,3,4,5]
 * 向右轮转 3 步: [5,6,7,1,2,3,4]
 * 1 2 3 4 5 6 7
 * 7 6 5 4 3 2 1
 * 7 6 5 1 2 3 4
 * 示例 2:
 * <p>
 * 输入：nums = [-1,-100,3,99], k = 2
 * 输出：[3,99,-1,-100]
 * 解释:
 * 向右轮转 1 步: [99,-1,-100,3]
 * 向右轮转 2 步: [3,99,-1,-100]
 * <p>
 * 使用空间复杂度 O(1)的方式进行处理
 *
 */
public class LunZhuanShuZu {


    public static void main(String[] args) {
//        rotate_self(new int[]{1, 2, 3, 4, 5, 6, 7}, 3);
//        rotate_self_1(new int[]{1, 2, 3, 4, 5, 6, 7}, 3);
        rotate_self_1(new int[]{-1, -100, 3, 99}, 2);
    }

    /**
     * -1
     * 3, -100, -1, 99
     * 1 2 3 4 5  6 k = 2
     * 2 3 4 5 6 1
     * 5 6 1 2 3 4
     * <
     * 1 2 3 4 5 6    k = 1
     * 6   5 4 3 2 1
     * 6  1 2 3 4 5
     *
     * @param nums
     * @param k
     */
    public static void rotate_self_1(int[] nums, int k) {

        int count = 1;
        int currentIdx = 0;
        int next = nums[k];
        while (count <= nums.length) {
            count++;
            int currentVal = nums[currentIdx];
            nums[currentIdx] = next;
            next = currentVal;

            int nextIdx = ((currentIdx + k) >= nums.length) ? (currentIdx + k - nums.length) : currentIdx + k;
            currentIdx = nextIdx;


            count++;
        }

    }


    class Solution {
        /**
         * 该方法基于如下的事实：当我们将数组的元素向右移动 k 次后，尾部 kmodn 个元素会移动至数组头部，其余元素向后移动 kmodn 个位置。
         * <p>
         * 该方法为数组的翻转：我们可以先将所有元素翻转，这样尾部的 kmodn 个元素就被移至数组头部，然后我们再翻转 [0,kmodn−1] 区间的元素和 [kmodn,n−1] 区间的元素即能得到最后的答案。
         * <p>
         * 我们以 n=7，k=3 为例进行如下展示：
         * <p>
         * 操作	结果
         * 原始数组	1 2 3 4 5 6 7
         * 翻转所有元素	7 6 5 4 3 2 1
         * 翻转 [0,kmodn−1] 区间的元素	5 6 7 4 3 2 1
         * 翻转 [kmodn,n−1] 区间的元素	5 6 7 1 2 3 4
         * <p>
         * <p>
         * 作者：力扣官方题解
         * 链接：https://leetcode.cn/problems/rotate-array/solutions/551039/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/
         * 来源：力扣（LeetCode）
         * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         *
         *
         * @param nums
         * @param k
         */
        public void rotate(int[] nums, int k) {
            k %= nums.length;
            reverse(nums, 0, nums.length - 1);
            reverse(nums, 0, k - 1);
            reverse(nums, k, nums.length - 1);
        }

        public void reverse(int[] nums, int start, int end) {
            while (start < end) {
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                start += 1;
                end -= 1;
            }
        }
    }


    //O(n)的方式
    public static void rotate_self(int[] nums, int k) {
        int[] result = new int[nums.length];

        int index = 0;
        //处理后几个
        for (int i = nums.length - k; i < nums.length; i++) {
            result[index++] = nums[i];
        }
        //处理前几个
        for (int i = 0; i < nums.length - k; i++) {
            result[i + k] = nums[i];
        }
        nums = result;
    }

}
